Vincent Neiger

PolSys, Sorbonne Université

Designing fast Guruswami-Sudan decoders using univariate polynomial matrix algorithms.

This talk revolves around algorithmic questions that have created strong and fruitful interactions between coding theorists and computer algebraists since the 1960s. We will mostly focus on decoding algorithms, and more specifically on their computational efficiency. A natural setting to start with is the unique decoding of Reed-Solomon codes, which highlights a rich body of related algorithms based on univariate polynomials, involving linear recurrence guessing via the Berlekamp-Massey algorithm, Hankel linear system solving, Padé approximations, and the extended Euclidean algorithm. We will gradually move towards more general decoders, notably with the Guruswami-Sudan approach for list decoding, and more general codes such as interleaved Reed-Solomon codes and Algebraic Geometry codes. We will present progress of the last two decades in these directions. It has been achieved via generalizations, based on univariate polynomial matrices, of the above body of algorithms: linear recurrences of matrices, structured linear systems, Hermite-Padé approximations and vector interpolation, and Popov form computations.

Documents : Slides

Magali Bardet

LITIS, Université de Rouen

Algebraic cryptanalysis in rank metric code-based cryptography.

In a first part, I will present two hard problems from coding theory that are used to build post-quantum cryptographic schemes: the MinRank problem and the Rank Decoding problem, that are related to codes in the rank metric. I will also introduce algebraic cryptanalysis, and in particular Gröbner basis, that is a powerfull tool to solve algebraic systems. It is well known that solving algebraic systems is hard, and that Gröbner basis computations have a doubly exponential complexity in the worst case. However, in most cases the cost is simply exponential, and can even be polynomial for particular systems.
In the second part, I will present various algebraic modelings for the MinRank and Rank Decoding problems, the link between them, analyse (when possible) the complexity of solving the algebraic systems, and present the consequences for cryptographic applications.

Gilles Zémor

Institut de Mathématiques de Bordeaux

Recent constructions of asymptotically good quantum LDPC codes.

It is commonly thought that large-scale quantum computers will require the use of quantum LDPC codes. Until relatively recently, it was not known whether quantum LDPC codes with a minimum distance that behave significantly better than the square root of the number of qubits exist. The discovery of quantum LDPC codes with not only linear distance but also non-vanishing rate was therefore quite a breakthrough.
We will present such a construction and discuss the algebraic tools that are involved, namely expansion in square complexes and robustness of classical tensor codes.

Documents : Notes